<head>
    <meta charset="UTF-8">
<title>算法提高 Pumping Stations</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div>【问题描述】</div>
<div>疯狂的科学家Mike申请了一份工作。他的任务是管理一个抽水站系统。</div>
<div>这个系统包含n个抽水站，抽水站被标号为1到n。连接两个抽水站的双向管道可以使水在任何一个方向流动（但同一时间水只能往一个方向流）。你知道每个管道的宽度&mdash;&mdash;每小时可以流过的最大水量。每个抽水站可以通过这些管道把水从一些站台抽向其他站台，同时在一小时内总的进水量等于总的出水量。</div>
<div>Mike的责任是用泵在这些站台之间输送水。遵循上述规则，可以在一小时内将一定数量的水通过管道（可能是通过其他站台）从站台a输送到站台b。在这期间，其他站台的水不能流入a，同时b站台的水也不能流出去。但是，任意多的水可以流出站台a，或者是流进站台b。如果一小时内有x升水流出站台a，Mike将获得额外的x元工资。</div>
<div>根据合同，Mike需要工作n-1天才能得到薪水。在第一天，他选择两个站台v_1和v_2，同时在一小时内，他将一定数量的水从v_1输送到v_2。然后，在第i天，Mike选择一个之前没有选过的站台v_i+1，再将一定数量的水在一小内从v_i输送到v_i+1。他在第i天输送的水的总量并不取决于他在第i-1天输送的水的总量。</div>
<div>Mike需要挣得尽可能多的钱，帮助迈克找到这样的一个排列v_1，v_2，&hellip;&hellip;，v_n使得麦克能够获得尽可能高的薪水。</div>
<div>【输入格式】</div>
<div>第一行读入两个整数n，m表示站台和管道的数量。</div>
<div>接下来m行每行三个整数a_i,b_i,c_i（a_i&ne;b_i）表示有一根管道连接站台a_i和b_i，并且它的容量是c_i。</div>
<div>保证任意两个站台之间最多有一根管道，任意两个站都可以通过管道到达。</div>
<div>【输出格式】</div>
<div>第一行一个整数&mdash;&mdash;麦克能够获得的最高的薪水。</div>
<div>在第二行输出n个用空格隔开的整数v_1，v_2，&hellip;&hellip;，v_n。如果有多解，输出任意一组。</div>
<p>【样例输入】</p>
<p>6 11</p>
<p>1 2 10</p>
<p>1 6 8</p>
<p>2 3 4</p>
<p>2 5 2</p>
<p>2 6 3</p>
<p>3 4 5</p>
<p>3 5 4</p>
<p>3 6 2</p>
<p>4 5 7</p>
<p>4 6 2</p>
<p>5 6 3</p>
<p>【样例输出】</p>
<div>77</div>
<div>6 2 1 5 3 4&nbsp;</div>
<p>【数据规模和约定】</p>
<div>对于40％的数据，n&le;30，m&le;350</div>
<div>对于60％的数据，n&le;80，m&le;1000</div>
<div>对于100％的数据，n&le;200，m&le;1000，1&le;c_i&le;100</div>